#pragma once

#include <stdio.h>

void Print(int* array, int size)
{
  for(int i = 0; i < size; i++){
    printf("%d ", array[i]);
  }
  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int tmp = *pa1;
  *pa1 = *pa2;
  *pa2 = tmp;
}

int GetMidIndex(int* array, int left, int right)
{
  int mid = (left + right) >> 1;
  if(array[left] > array[mid]){
    if(array[left] < array[right]) return left;
    else {
      if(array[mid] > array[right]) return mid;
      else return right;
    }
  }
  else {
    if(array[mid] < array[right]) return mid;
    else {
      if(array[left] < array[right]) return left;
      else return right;
    }
  }
}

//左右指针法
int Part1(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array, left, right)]);
  int keyi = left;
  int begin = left;
  int end = right;
  while(begin < end){
    while(begin < end && array[end] >= array[keyi]) end --;
    while(begin < end && array[begin] <= array[keyi]) begin ++;
    if(begin < end) Swap(&array[begin], &array[end]);
    else Swap(&array[begin], &array[keyi]);
  }

  return begin;
}

//挖坑法
int Part2(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array, left, right)]);
  int key = array[left];
  int begin = left;
  int end = right;
  int hole = begin;
  while(begin < end){
    while(begin < end && array[end] >= key) end --;
    array[hole] = array[end];
    hole = end;
    while(begin < end && array[begin] <= key) begin ++;
    array[hole] = array[begin];
    hole = begin;
    if(begin == end) array[hole] = key;
  }

  return hole;
}

//前后指针法
int Part3(int* array, int left, int right)
{
  Swap(&array[left], &array[GetMidIndex(array, left, right)]);
  int keyi = left;
  int prev = left;
  int curr = left + 1;
  while(curr <= right){
    if(array[curr] < array[keyi] && ++prev != curr) Swap(&array[prev], &array[curr]);
    curr ++;
  }

  Swap(&array[keyi], &array[prev]);
  return prev;
}

void _QuickSort(int* array, int left, int right)
{
  if(left >= right) return ;
  
  //int meeti = Part1(array, left, right);
  //int meeti = Part2(array, left, right);
  int meeti = Part3(array, left, right);

  _QuickSort(array, left, meeti - 1);
  _QuickSort(array, meeti + 1, right);
}

void QuickSort(int* array, int size)
{
  _QuickSort(array, 0, size - 1);
}

void QuickSortNonR(int* array, int size)
{
  int hh = 0;
  int tt = 0;
  int q[100000];
  
  //插入左右区间
  q[tt++] = 0;
  q[tt++] = size - 1;

  while(hh < tt){
    int left = q[hh++];
    int right = q[hh++];
    
    int meeti = Part1(array, left, right);

    if(left < meeti - 1) {
      q[tt++] = left;
      q[tt++] = meeti - 1;
    }

    if(meeti + 1 < right){
      q[tt++] = meeti + 1;
      q[tt++] = right;
    }
  }
}
